home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_100 / 101_01 / hstone.c < prev    next >
Encoding:
Text File  |  1985-11-13  |  12.6 KB  |  433 lines
  1. /*
  2.             ===
  3.     "STONE" --- H19  Version (for H19/Z19/H89/Z89 ONLY)
  4.             ===
  5.  
  6.     (otherwise known as "Awari")
  7.  
  8.     This version written by:
  9.  
  10.     Terry Hayes & Clark Baker
  11.     Real-Time Systems Group
  12.     MIT Lab for Computer Science
  13.  
  14.     Hacked up a little by Leor Zolman and Steve Ward
  15.     (Steve did all the neat H19 display hackery!)
  16.  
  17.     The algorithm used for STONE is a common one
  18.     to Artificial Intelligence people: the "Alpha-
  19.     Beta" pruning heuristic. By searching up and down 
  20.     a tree of possible moves and keeping record of
  21.     the minimum and maximum scores from the
  22.     terminal static evaluations, it becomes possible
  23.     to pinpoint move variations which can in no way
  24.     affect the outcome of the search. Thus, those
  25.     variations can be simply discarded, saving 
  26.     expensive static evaluation time.
  27.  
  28.     THIS is the kind of program that lets C show its
  29.     stuff; Powerful expression operators and recursion
  30.     combine to let a powerful algorithm be implemented
  31.     painlessly.
  32.  
  33.     And it's fun to play!
  34.  
  35.  
  36.     Rules of the game:
  37.  
  38.     Each player has six pits in front of him and a
  39.     "home" pit on one side (the computer's home pit
  40.     is on the left; your home pit is on the right.)
  41.  
  42.     At the start of the game, all pits except the home
  43.     pits are filled with n stones, where n can be anything
  44.     from 1 to 6.
  45.  
  46.     To make a move, a player picks one of the six pits
  47.     on his side of the board that has stones in it, and
  48.     redistributes the stones one-by-one going counter-
  49.     clockwise around the board, starting with the pit
  50.     following the one picked. The opponent's HOME pit is
  51.     never deposited into.
  52.  
  53.     If the LAST stone happens to fall in that player's
  54.     home pit, he moves again.
  55.  
  56.     If the LAST stone falls into an empty pit on the
  57.     moving player's side of  board, then any stones in the
  58.     pit OPPOSITE to that go into the moving
  59.     player's home pit.
  60.  
  61.     When either player clears the six pits on his
  62.     side of the board, the game is over. The other player
  63.     takes all stones in his six pits and places them in
  64.     his home pit. Then, the player with the most stones
  65.     in his home pit is the winner.
  66.  
  67.     The six pits on the human side are numbered one
  68.     to six from left to right; the six pits on the    
  69.     computer's side are numbered one to six right-to-
  70.     left.
  71.  
  72.     The standard game seems to be with three stones;
  73.     Less stones make it somewhat easier (for both you
  74.     AND the computer), while more stones complicate
  75.     the game. As far as difficulty goes, well...it
  76.     USED to be on a scale of 1 to 50, but I couldn't
  77.     win it at level 1. So I changed it to 1-300, and
  78.     couldn't win at level 1. So I changed it to 1-1000,
  79.     and if I STILL can't win it at level 1, I think
  80.     I'm gonna commit suicide.
  81.  
  82.     Good Luck!!!
  83. */
  84.  
  85. unsigned total;
  86. char string[80];
  87.  
  88. unsigned COUNT, Seed;
  89. int NUM;
  90.  
  91. int holex[14];
  92. int holey[14];
  93. int stonex[48];
  94. int stoney[48];
  95.  
  96. exinit()
  97.  {    initw(holex, "7,10,10,10,10,10,10,8,4,4,4,4,4,4");
  98.     initw(holey, "7,16,24,32,40,48,56,66,56,48,40,32,24,16");
  99.     initw(stonex, "0,0,0,-1,1,1,1,-1,-1,1,1,0,0,-1,-1,-2,-2,-2,-2,\
  100.      -2,-3,-3,-3,-3,-3,-1,0,-2,1,-3,2,2,2,2,3,3,-4,-4,-4,-4,3,2,3,\
  101.      2,3,3,-4,-4");
  102.     initw(stoney, "0,1,-1,0,0,-1,1,-1,1,-2,2,-2,2,-2,2,0,-1,1,-2,2,\
  103.      0,-1,1,-2,2,-3,-3,-3,-3,-3,0,-1,-2,1,0,-1,-1,0,-2,1,1,2,-2,-3,\
  104.      2,-3,2,-3");
  105.  }
  106.  
  107. putchar(ch)
  108.  {    
  109.     bios(4,ch);
  110.  }
  111.  
  112. dance(y, x)
  113.  {    int i,j,k;
  114.     k = 30;
  115.     puts("\033q\033F");
  116.     while (!bios(2))
  117.      { display(y,x);
  118.        for (i=0; i<k; i++) putchar((i+j) & 3? ' ':'^'); j++; }
  119.     display(y, x);
  120.     for (i=0; i<k; i++) putchar(' ');
  121.  }
  122.  
  123.  
  124. main(argc,argv)
  125. {
  126.         int  hum,com,y,inp;
  127.         char board[14];
  128.     for (y=0; y<1000; y++) Seed += stonex[y];
  129.     srand(Seed);
  130.     exinit();
  131.  
  132. new:    printf("\033E\033q\033G");
  133.     printf("New Game:\r\nDifficulty (1-1000, or q to quit): ");
  134.     inp = atoi(gets(string));
  135.     if (inp < 1) { printf("\033z"); return; }
  136.     if (inp>1000) goto new;
  137.     printf("Number of stones (1-6): ");
  138.     NUM = atoi(gets(string));
  139.     COUNT = inp * 65;
  140.     NewBD();
  141.     initb(board);
  142.     display(21,50); printf("\033p Difficulty: %d \033q", inp);
  143.     display(19,0);
  144.     printf("Do you want to go first (y or n)? ");
  145.     inp = toupper(getchar());
  146.         printf("\033l\n\n");
  147.         if (inp ==  'N') goto first;
  148.         y = 0;
  149.         while(notdone(board)) {
  150. again:        display(20,10);
  151.                 printf("\033G\033p Your move:   \b\b");
  152.                 for (;;) {
  153.             dance(20, 40); puts("\033p"); display(20,22);
  154.                         inp = getchar() - '0';
  155.             if (toupper(inp+'0')=='Q')goto new;
  156.                         if (inp < 1 || inp > 6 || !board[inp])
  157.              { putchar(7); goto again; }
  158.                         y++;
  159.                         break;
  160.                 }
  161.         puts("\033q");
  162.                 if (!dmove(board,inp)) continue;
  163. first:        display(20,10); rptc(' ', 30);
  164.                 y = 0;
  165.                 while (notdone(board)) {
  166.             display(21, 10);
  167.                     printf("\033p I'm thinking \033q");
  168.                         inp = comp(board);
  169.             display(21,10); rptc(' ', 30);
  170.             display(22,10);
  171.                         printf("\033p Computer moves: ");
  172.                         printf("%d \033q",inp-7);
  173.                         y++;
  174.                         if (dmove(board,inp)) break;
  175.             display(22,10); rptc(' ', 30);
  176.                 }
  177.                 y = 0;
  178.         }
  179.         com = board[0]; 
  180.         hum = board[7];
  181.         for (inp = 1; inp < 7; inp++) { 
  182.                 hum += board[inp]; 
  183.                 com += board[inp+7]; 
  184.         }
  185.     display(23,10);
  186.         printf("\033p Score:   me %d  you %d . . . ",com,hum);
  187.     if (com>hum) switch (rand() % 4) {
  188.         case 0: printf("Gotcha!!");
  189.             break;
  190.         case 1:    printf("Chalk one up for the good guys!");
  191.             break;
  192.         case 2: printf("Automation does it again!");
  193.             break;
  194.         case 3: printf("I LOVE to WIN!");
  195.         }
  196.     else if (hum==com) printf("How frustrating!!");
  197.     else printf("Big Deal! Try a REAL difficulty!");
  198.     printf(" \033q\033G");
  199.     display(19,0);
  200.     sleep(5);
  201.         printf("\033p New Game (y/n): \033q\033K");
  202.     dance(19,40);
  203.     if (toupper(getchar()) == 'Y') goto new;
  204.     display(23,0);
  205.     printf("\033z");
  206.         exit();
  207. }
  208.  
  209. mod(i,j)  int i,j; 
  210. {
  211.     ++i;
  212.         if (i == 7) return( j ? 7 : 8);
  213.         if (i > 13) return ( j ? 1 : 0);
  214.         return(i);
  215. }
  216.  
  217. initb(board)  char *board; 
  218. {
  219.          int i,j;
  220.         for (i= 0; i <14; ++i)
  221.      { board[i]=0;
  222.        if (i != 0 && i != 7) for (j = 0; j < NUM; j++) incpit(board,i); }
  223.         return;
  224. }
  225.  
  226. comp(board)  char *board; 
  227. {
  228.          int score;
  229.         int bestscore,best;
  230.         char temp[14];
  231.          int i;
  232.         unsigned nodes;
  233.         total = 0;
  234.  
  235.         if ((i = countnodes(board,8)) == 1)
  236.                 for (best = 8; best < 14; ++best)
  237.                         if (board[best]) return(best);
  238.         nodes = COUNT/i;
  239.         bestscore = -10000;
  240.         for (i = 13; i > 7; --i) if (board[i]) {
  241.                 score = mmove(board,temp,i);
  242.         score = comp1( temp, score, nodes, bestscore, 10000);
  243.                 if (score > bestscore) {
  244.                         bestscore = score;
  245.                         best = i;
  246.                 }
  247.         }
  248.     display(19,10);
  249.         if (bestscore > 1000)
  250.         puts("\033p I'VE GOT YOU! \033q\n");
  251.         if (bestscore < -1000)
  252.                 printf("\033p YOU'VE GOT ME! \033q\n");
  253.         return(best);
  254. }
  255.  
  256. comp1(board,who,count,alpha,beta)
  257.  char *board; int who; int alpha,beta;
  258. unsigned count; 
  259. {
  260.          int i;
  261.         int turn,new;
  262.         char temp[14];
  263.         unsigned nodes;
  264.         if (count < 1) {
  265.                 new = board[0]-board[7];
  266.                 for (i = 1; i < 7; ++i) { turn = min(7-i,board[i]);
  267.                                           new -= 2*turn - board[i]; }
  268.                 for (i = 8; i < 14; ++i) { turn = min(14-i,board[i]);
  269.                                            new += 2*turn - board[i]; }
  270.                 if (board[0] > 6*NUM) new += 1000;
  271.                 if (board[7] > 6*NUM) new -= 1000;
  272.                 return(new);
  273.         }
  274.         if (!notdone(board)) {
  275.                 new = board[0]+board[8]+board[9]+board[10]
  276.                     +board[11]+board[12]+board[13]-board[1]-board[2]
  277.                     -board[3]-board[4]-board[5]-board[6]-board[7];
  278.                 if ( new < 0) return (new - 1000);
  279.                 if ( new > 0) return (new + 1000);
  280.                 return(0);
  281.         }
  282.         nodes = count/countnodes(board,8-who*7);
  283.         for (i = 7*(1-who)+6; i > 7*(1-who); --i)
  284.                 if (board[i]) {
  285.                         turn = mmove(board,temp,i);
  286.                         new = comp1(temp,(turn? 1-who: who),nodes,alpha,beta);
  287.                         if (who) {
  288.                            beta = min(new,beta);
  289.                            if (beta <= alpha) return(beta); }
  290.                         else { 
  291.                             alpha = max(new,alpha);
  292.                             if (alpha >= beta) return(alpha); }
  293.                 }
  294.         return(who ? beta : alpha);
  295. }
  296.  
  297. min(i,j)  int i,j; 
  298. {
  299.         return(i < j ? i : j);
  300. }
  301.  
  302. max(i,j)  int i,j; 
  303. {
  304.         return(i > j ? i : j);
  305. }
  306.  
  307. notdone(board)  char *board; 
  308. {
  309.     return (board[1] || board[2] || board[3] || board[4]
  310.         || board[5] || board[6]) &&
  311.            (board[8] || board[9] || board[10] || board[11]
  312.         || board[12] || board[13]);
  313. }
  314.  
  315. countnodes(board,start) int start; char *board; 
  316. {
  317.         int i;
  318.         int num;
  319.         num = 0;
  320.     for (i = start; i< start + 6; ++i)
  321.         num += (board[i] ? 1 : 0);
  322.         return(num);
  323. }
  324.  
  325. incpit(board,pit) char *board; int pit; 
  326. {
  327.     display(1+holex[pit]+stonex[board[pit]],
  328.         3+holey[pit] +stoney[board[pit]]);
  329.     printf("\033F^\033G");
  330.     board[pit]++;
  331. }
  332.  
  333. display(x,y) int x,y; 
  334. {
  335.     printf("\033Y%c%c",x+32,y+32);
  336. }
  337.  
  338. decpit(board,pit) char *board; int pit; 
  339. {
  340.     board[pit]--;
  341.     display(1+holex[pit]+stonex[board[pit]],
  342.         3+holey[pit] +stoney[board[pit]]);
  343.     putchar(' ');
  344. }
  345.  
  346.  
  347. rpt(cc, n)
  348.  {    while (n--) printf(cc); }
  349.  
  350. rptc(cc, n)
  351.  {    while (n--) putchar(cc); }
  352.  
  353. nb1(n)
  354.  {    rpt("ii    q        p  q       p q       p q       p q       p q       p q       p  q        p  ii\n\r", n); }
  355.  
  356. NewBD()
  357.  {    printf("\033H\033J\033p\033F");
  358.     rptc('i', 77);
  359.     printf("\n\rii"); rptc(' ',73);
  360.     printf("ii\n\rii");
  361.     printf("       ME        6       5       4       3");
  362.     printf("       2       1               ii\n\rii    qr      _p ");
  363.     rpt(" qr     _p", 6); printf("            ii\n\r");
  364.     printf("ii    q        p  q       p q       p q       p q       p q       p q       p  qr      _p  ii\n\r");
  365.     nb1(2);
  366.     printf("ii    q        p  _q     pr _q     pr _q     pr _q     pr _q     pr _q     pr  q        p  ii\n\r");
  367.     printf("ii    q        p                                                   q        p  ii\n\r");
  368.  
  369.     printf("ii    q        p  qr     _p qr     _p qr     _p qr     _p qr     _p qr     _p  q        p  ii\n\r");
  370.     nb1(2);
  371.     printf("ii    _q      pr  q       p q       p q       p q       p q       p q       p  q        p  ii\n\r");
  372.     printf("ii              _q     pr _q     pr _q     pr _q     pr _q     pr _q     pr  _q      pr  ii\n\r");
  373.     printf("ii                 1       2       3       4       5       6        YOU    ii\n\r");
  374.     printf("ii                                                                         ii\n\r");
  375.     rptc('i', 77);
  376.     printf("\033G\033q");
  377.  }
  378.  
  379. sleep(n)
  380.  {    int i;
  381.     while (n--) for (i=12000; i--;); }
  382.  
  383. dmove(new,move) char *new,move; 
  384. {    int i;
  385.     int j; 
  386.     int who;
  387.     if ((move < 1) || (move > 13) || (move == 7) || !new[move])
  388.         printf("Bad arg to mmove: %d",move);
  389.     who = (move < 7 ? 1 : 0);
  390.     i = new[move];
  391.     for (j = 0; j < i; j++) decpit(new,move);
  392.     sleep(1);
  393.     while (i--) {
  394.         move = mod(move,who);
  395.         incpit(new,move);
  396.         putchar(7);
  397.         sleep(1);
  398.     }
  399.     if (new[move] == 1 && who == (move < 7 ? 1 : 0) && move && move != 7)
  400.         while(new[14-move]) { 
  401.             decpit(new,14-move);
  402.             incpit(new,who*7);
  403.         }
  404.     if (move == 0 || move == 7) return(0); 
  405.     else return(1);
  406. }
  407.  
  408.  
  409. mmove(old,new,move) char *old;  char *new; int move; 
  410. {
  411.          int i; 
  412.         int who;
  413.         total++;
  414.  
  415.         for (i = 0; i < 14; ++i) new[i] = old[i];
  416.         if ((move < 1) || (move > 13) || (move == 7) || !new[move])
  417.                 printf("Bad arg to mmove: %d",move);
  418.         who = (move < 7 ? 1 : 0);
  419.         i = old[move];
  420.         new[move] = 0;
  421.         while (i--) {
  422.                 move = mod(move,who);
  423.         ++new[move];
  424.         }
  425.         if (new[move] == 1 && who == (move < 7 ? 1 : 0) && move && move != 7)
  426.         { 
  427.                 new[who*7] += new[14-move];
  428.                 new[14-move] = 0;
  429.         }
  430.         if (move == 0 || move == 7) return(0); 
  431.         else return(1);
  432. }
  433.